/*
 * @lc app=leetcode.cn id=76 lang=java
 *
 * [76] 最小覆盖子串
 */

// @lc code=start

import java.util.*;

class Solution {
    Map<Character, Integer> s_m = new HashMap<>();
    Map<Character, Integer> t_m = new HashMap<>();
    
    public String minWindow(String s, String t) {
        int s_len = s.length();
        int t_len = t.length();

        for(int i=0;i<t_len;i++){
            Character temp = t.charAt(i);
            t_m.put(temp, t_m.getOrDefault(temp, 0) + 1); 
        }

        int l=0,r=0;
        int min_len = Integer.MAX_VALUE;
        int ans_l=-1, ans_r = -1;

        while (r<s_len) {
            if(t_m.containsKey(s.charAt(r))){
                s_m.put(s.charAt(r), s_m.getOrDefault(s.charAt(r), 0)+1);
            }
            while (l<=r && this.check()) {
                if(r - l < min_len){
                    ans_r = r;
                    ans_l = l;
                    min_len = ans_r - ans_l;
                }
                if(t_m.containsKey(s.charAt(l))){
                    s_m.put(s.charAt(l), s_m.getOrDefault(s.charAt(l),0) - 1);
                }
                l++;
            }
            r++;
        }
        return ans_r == -1 ? "" : s.substring(ans_l, ans_r+1);
    }
    private boolean check(){
        Iterator iterator = t_m.entrySet().iterator();

        while (iterator.hasNext()) {
           Map.Entry entry = (Map.Entry) iterator.next();
           Character key = (Character)entry.getKey();
           Integer value = (Integer)entry.getValue();
            if(s_m.getOrDefault(key, 0) < value){
                return false;
            }
        }
        return true;
    }
}
// @lc code=end

